package chapter01;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    /**
     * 回溯法
     * 递归条件
     *      1) 小列表中数字之加 > target
     *          直接返回
     *      2) 小列表中数字之加 == target
     *          将小列表加入大列表
     *          返回
     *      3) 小列表中数字之加 < target
     *          从candidates[0~length-1]遍历数字，将数字加入小列表中
     *          加入小列表中的数字在进入下一次循环时，要将上一次加入的数字从小列表中移除
     * 细节
     *      小列表中为了避免重复元素，如[2,3] [3,2]
     *      进行规定：小列表中元素非递减组织 即list[list.length-1] <= candidates[i]
     */
    List<List<Integer>> intList=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combinationSum(candidates,target,0,new ArrayList<>());
        return intList;
    }

    public void combinationSum(int[] candidates, int target,int count,List<Integer> res){
        if(count==target){
            intList.add(new ArrayList<>(res));
            return;
        }
        if(count>target){
            return;
        }
        int length=candidates.length;
        for(int i=0;i<length;i++){
            if(res.size()==0||res.get(res.size()-1)<=candidates[i]) {
                res.add(candidates[i]);
                combinationSum(candidates, target, count + candidates[i], res);
                res.remove(res.size() - 1);
            }
        }
    }
}
